package cc.willrock.algorithm.sort;

import java.util.Arrays;

public class HeapSort {
	
	/*
	 * algorithm in a nutshell
	 * 
	 * 最好O(n*log(n))
	 * 平均O(n×log(n))
	 * 最坏O(n×log(n))
	 *  
	 */
	public static int [] sort(int[] a) {
		int n = a.length;
		int temp = 0;
		
		//buildHeap
		for (int i = (n / 2)-1; i >= 0; i--)
			heapify(a, i, n);

		for (int i = n - 1; i >= 0; i--) {
			temp = a[i ];
			a[i ] = a[0];
			a[0] = temp;

			heapify(a, 0, i );
		}
		return a;
	}

	//非递归
	public static void heapify2(int[] a, int i, int n) {
		int j = 0;
		int temp = 0;

		temp = a[i];
		j = 2 * i + 1;

		while (j <= n - 1) {
			if (j < n - 1 && a[j] < a[j + 1])
				j++;

			if (temp >= a[j])
				break;

			a[(j - 1) / 2] = a[j];

			j = 2 * j + 1;
		}

		a[(j - 1) / 2] = temp;
	}
	
	
	//递归
	public static void heapify(int[] a, int i, int n) {
		int left = 2*i+1;
		int right = 2*i+2;
		int largest = -1;
		if(left<n && a[left]>a[i]){
			largest = left;
		}else{
			largest = i;
		}
		if(right<n && a[right]>a[largest]){
			largest = right;
		}
		if(largest!=i){
			int temp = a[i];
			a[i] = a[largest];
			a[largest]=temp;
			
			heapify(a,largest,n);
		}
	}

	
	public static void main(String[] args) {
	    //int[] a = {15,9,8,1,4,11,7,12,13,6,5,3,16,2,10,14};
		int[] a = { 5, 3, 16, 2,10, 14 };
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(sort(a)));
	}
}
